The present invention relates to the field of measurement and data acquisition, and more particularly to the analysis of a surface of an object by generation or mapping of a point set on a Riemannian manifold or surface of the object and analyzing data values on the mapped point set to characterize the object.
Many scientific and engineering tasks involve exploring, i.e., sampling or scanning, a region, such as an image, surface, or object, to acquire data characterizing the region. Examples of such tasks include parts inspection for automated manufacturing systems, alignment tasks for automated assembly systems, and detection, recognition, and location tasks in machine vision and motion control systems, among others. Another application relates to the determination of integrals of smooth functions defined on Riemannian geometries embedded in Rn, i.e., in multi-dimensional real-space, via sums of function values at well-chosen sampling points. Yet another domain application relates to the exploration and characterization of unknown spaces.
In a typical sampling or scanning system a computer system is coupled to a sensor, such as a camera, which is operable to acquire optical, image, or other information from a target object or surface. The computer system may take any of various forms. The system may also include hardware and corresponding software which is operable to move one or both of the sensor and the target object to perform the scan or measurement. In robotics and motion planning an understanding of the underlying geometry of space is important. Various techniques have been developed to scan regions under various constraints or toward specific goals. In many cases the geometry is known in advance and a specific goal is desired, such as object recognition and/or characterization. In others the space in question may not be characterized, i.e., the nature of the space may be unknown. Exploration of such a space may involve goals such as determining the dimensionality and structure of a space with unknown underlying geometry, or finding critical points of a high-dimensional space.
Typical applications of scanning spaces of known geometry include, but are not limited to: mine-countermeasure missions, continental shelf oceanographic mapping, contamination cleanup, floor scrubbing, crop plowing, non-destructive testing, and bridge inspections, among others. Many of these applications attempt efficient coverage of the space, and so involve determining a coverage plan for the scan region. Most coverage planners are still based on heuristics and the smoothness of the developed trajectories is rarely an issue.
There are many coverage algorithms. In many cases the goal is to guide a robot or sensor to explore or to act within an environment. See, for example, J. Colgrave, A. Branch, xe2x80x9cA Case Study of Autonomous Household Vacuum Cleanerxe2x80x9d, AIAA/NASA CIRFFSS, 1994. See also M. Ollis, A. Stentz, xe2x80x9cFirst Results in Vision-Based Crop Line Trackingxe2x80x9d, IEEE International Conference on Robotics and Automation, 1996.
One promising method in motion planning is based on Morse functions. These procedures look at the critical points of a Morse function to denote the topological changes in a given space. See, for example, Howie Choset, Ercan Acar, Alfred A. Rizzi, Jonathan Luntz, xe2x80x9cExact Cellular Decompositions in Terms of Critical Points of Morse Functionsxe2x80x9d. See also Ercan U. Acar, Howie Choset, xe2x80x9cCritical Point Sensing in Unknown Environmentsxe2x80x9d. However, Morse functions find their primary use with regard to the scanning of un-smooth surfaces, and so are not generally useful for many applications.
Exploration tasks often relate to characterization of unknown spaces. One approach to efficient exploration of a surface or space is based upon Low Discrepancy Sequences (LDS), described below in some detail. However, current techniques generally involve generation of LDSs in simple Euclidean spaces, which may not be appropriate for more complex applications.
Therefore, improved systems and methods are desired for generating a sampling point set, such as a Low Discrepancy Sequence, in a region or on a manifold or surface of an object.
The present invention comprises various embodiments of a system, method, and memory medium for analyzing a surface, wherein the surface may be a surface of an object, a region, and/or an n-dimensional volume. The surface may also be a Riemannian manifold or an n-dimensional space describing degrees of freedom of an object or device, such as a motion device, e.g., a robotic arm. The method may involve generating a point set or sequence on the surface, acquiring data or taking measurements of the surface at these sample points, and analyzing the measured data to characterize the surface.
The method may include generating a sequence, such as a Low Discrepancy Sequence, within a region or space in which the surface is defined. The sequence may be used for characterizing the surface, such as a high-dimensional space, or for motion planning. Embodiments of the invention include a method for generating a Low Discrepancy Sequence in a Riemannian manifold, e.g., on an n-dimensional surface.
Specifically, an embodiment of the method is described in which a Low Discrepancy Sequence is generated on an n-dimensional space, for example, a unit square, then mapped to the manifold or surface. It is also contemplated that other sequences of points may be mapped in a similar manner, and that regions other than the unit n-square may be used. In one embodiment, the manifold may be a Riemannian manifold. In other words, the manifold may be characterized by a distance-like metric.
In one embodiment, data may be received describing a surface which is defined in a bounded n-dimensional space, also referred to as a bounded n-space. In one embodiment, the bounded n-dimensional space may comprise a unit square. In another embodiment, the bounded n-dimensional space may comprise a unit cube. As mentioned above, in various other embodiments, the bounded n-dimensional space may comprise other geometries, including unit hyper-cubes, or unit n-cubes of dimensionalities greater than 3, as well as n-dimensional rectangles, spheres, or any other geometrical region. In one embodiment, the surface may further be embedded in an m-dimensional space, where m greater than n. In other words, the surface may be parameterized in terms of a higher dimensional space according to an embedding function x( ).
The received data may include a Riemannian metric characterizing the surface or manifold. In one embodiment, the surface may comprise an image, and the received data may further comprise an intensity function describing the image, e.g., describing pixel information of the image.
A diffeomorphism f of the bounded n-space may be determined. As is well known in the art, a diffeomorphism may be considered a mapping between two spaces which preserves differentiability of a mapped function.
An inverse transform fxe2x88x921 of the determined diffeomorphism may be computed. Then, a plurality of points in the bounded n-space may be selected or determined. In one embodiment, the plurality of points may comprise a Low Discrepancy Sequence. It should be noted that although selection of a Low Discrepancy Sequence of points is an exemplary use of the method, any other point set may be used as desired.
In response to the selection of the plurality of points, the plurality of points may be mapped onto the surface via x(fxe2x88x921) to generate a mapped plurality of points, e.g., a mapped Low Discrepancy Sequence. Note that the function x(fxe2x88x921) may be a functional concatenation of the embedding function x( ) and the inverse transform of the diffeomorphism, fxe2x88x921.
The surface may be sampled or measured using at least a subset of the mapped plurality of points. In other words, measurements may be made at one or more of the mapped plurality of points, thereby generating one or more samples of the surface.
Finally, the generated samples of the surface may be analyzed to determine one or more characteristics of the surface. For example, in one embodiment, the surface may comprise a surface of an object, and the analyzing may comprise analyzing the samples of the surface to determine one or more characteristics of the object.
It should be noted that in some embodiments, the mapped plurality of points, e.g., the mapped Low Discrepancy Sequence, may simply be output for later use by the system or by other systems. In other words, the sampling and/or analyzing may be performed by other systems, or at a later time. In one embodiment, outputting the mapped points (Low Discrepancy Sequence) may comprise storing the Sequence for later use. In another embodiment, outputting the mapped Low Discrepancy Sequence may comprise displaying the sequence on a display device.
Thus, by using the above-described method, a plurality of points, e.g., a Low Discrepancy Sequence, generated on a unit square (or other suitable geometry) may be mapped to a surface, such as an abstract surface or manifold. It should be noted that any point set generated on the unit square (or other suitable geometry) may be mapped in this way. This mapped plurality of points may operate to ideally represent or characterize the surface, wherein measurements taken at these mapped points indicate characteristics of the surface.
In one embodiment, the above embodiment may be used to generate a scan path for a scanning application, such as a six degree of freedom alignment problem, for example. Other applications may include determination of scanning sequences for one or more robotic arms, where the scan space may describe degrees of freedom for the robotic arms, among others. For example, the scan space for the robotic arm may be a 6-dimensional space representing 3 positional degrees of freedom, and 3 directional or orientation degrees of freedom. Alternately, the degrees of freedom may relate to the degrees of freedom of joints or other articulated components of the arm. In one embodiment, the robotic arm may include a directional sensor, and the sampling may include measuring a vector field at one or more of the mapped plurality of points. One example of such an application relates to the location of an acoustic source via discrete sampling of sound strength and direction, such as by a directional microphone.
One of the most straightforward applications for Low Discrepancy Sequences are calculations of integrals of smooth functions defined on Riemannian geometries embedded in Rm. The replacement of integrals by sums of function values of well-chosen sampling points offers the same advantages as those based on low-discrepancy sets defined in unit cubes.
Another application field for Low Discrepancy Sequences is image processing, in which an intensity function of an image may be reinterpreted as a surface. In other words, the surface may comprise an image. Sampling of the image may comprise using or measuring pixel values at pixel locations corresponding to the mapped plurality of points. It should also be noted that in this embodiment, sampling may not necessarily involve measurement with a sensor, but rather may refer to calculation of an intensity value (or other pixel-related quantity) based on a function, e.g., an intensity function. The computed samples may then be analyzed to determine characteristics of the image. In one embodiment, the image may comprise information related to an object, where the analyzing may be performed to determine one or more characteristics of the object.
A Riemannian metric for the surface based on the intensity function may be determined, as well as a diffeomorphism representing information contained in the intensity function. In real applications, the integrals may be replaced with sums of function values. More importantly, the inverse diffeomorphism in conjunction with appropriate sampling strategies in the unit square may allow an induced sampling of a given image content. Thus, an image may be considered an abstract Riemannian surface or manifold.
It should be noted that although typical images are two-dimensional images, higher dimensional images are also contemplated. For example, complex multi-dimensional data sets may be considered images, and the methods described herein may be used to explore and characterize the data sets, or objects and features contained therein. Examples of 3-dimensional images include 3 d medical images, and 3 d seismic images, among others. It is also contemplated that data sets represented by even higher dimensional images (4 d and above) may be characterized by various embodiments of the present invention. In other words, any data set may be represented by an image of suitable dimensionality.
The intensity values at selected points may describe the image content in an efficient manner and may be used to compress an image or to characterize its content. To a certain extent, the resulting description can be regarded as a generalized edge detector that is highly optimized for a specific image. Potential applications can be found in pattern matching where a given template should be characterized by a small amount of pixels, to speed up successive search operations. The use of low-discrepancy sets offers the advantages mentioned before.
In one embodiment, data may be received describing an image which is defined in a bounded n-dimensional space, or n-space, and which may be embedded in an m-dimensional space, or m-space via an embedding function x( ), where m greater than n. In one embodiment, the bounded n-space may comprise a unit square (i.e., n=2). In other embodiments the bounded n-space may comprise a unit cube (n=3), a unit hyper-cube (n=4), or a unit n-cube where n greater than 4. It is noted that the bounded n-space may not be limited to unit n-cubes, but may also comprise any other suitable geometry, including a unit n-sphere, rectangles of various dimensionalities, or any other geometry, as desired. It is also noted that the n-space needn""t be of unit size, but may be of any size appropriate for the application or image under consideration.
In one embodiment, the received data may include an intensity function, as mentioned above. For example, for a gray-scale image, the intensity function may describe the gray-scale pixel value at each point in the image. Similarly, for a color image, the intensity function may provide pixel data for each point in the image.
A diffeomorphism (f,g) of the n-space may then be determined. As is well known in the art, a diffeomorphism may be considered a mapping between two spaces which preserves differentiability of a mapped function.
An inverse transform (fxe2x88x921,gxe2x88x921) of the determined diffeomorphism may be computed. Then, a plurality of points in the bounded n-space may be selected or determined. In one embodiment, the plurality of points may comprise a Low Discrepancy Sequence. It should be noted that although selection of a Low Discrepancy Sequence of points is an exemplary use of the method, any other point set may be used as desired.
After the selection of the plurality of points, the plurality of points may be mapped onto the surface via x(fxe2x88x921,gxe2x88x921) to generate a mapped plurality of points, e.g., a mapped Low Discrepancy Sequence. Note that the function x(fxe2x88x921,gxe2x88x921) may be a functional concatenation of the embedding function x( )and the inverse transform of the diffeomorphism, (fxe2x88x921,gxe2x88x921).
Finally, the mapped plurality of points may be analyzed to determine one or more characteristics of the image. In one embodiment, the mapped plurality of points may be analyzed to detect edges in the image. In other embodiments, analyzing the mapped plurality of points may include performing pattern recognition, where features or objects comprised or represented in the image may be detected and/or characterized.
Yet another application of the method relates to a fiber optic array alignment problem. Given an array of fibers where a second array of theses fibers must be aligned accurately. Typically, lasers are applied and the intensity of these beams may be measured to align the arrays.
Said another way, the surface may comprise a multi-dimensional space describing degrees of freedom for a motion stage, or for first and/or second motion stages, where the first and second motion stages couple respectively to first and second optical fibers (or groups of optical fibers). A laser beam may be directed through the first optical fiber. Samples may be taken at a plurality of points in the search space, where the sampling includes measuring the laser beam intensity through the second optical fiber at one or more of the mapped plurality of points. One or both of the first and second motion stages may be moved until the measured laser beam intensity indicates that the optical fibers are substantially aligned.
It should be noted that the above examples are meant to be illustrative, and are not intended to limit the domain of applicability of the method.
A system may implement any of the above methods for generating a Low Discrepancy Sequence in a Riemannian Manifold or surface and for scanning or analyzing the surface. The system may comprise a computer system coupled to a sensor. An embodiment of the system may also include a motion control element, or actuator. The computer system may comprise a CPU and a memory medium, or programmable logic, which is operable to store a scanning or analysis program that implements one of the above methods. An embodiment of each of the above invention(s) may also be a software program or programs stored on a memory medium.